A programmable logic device (PLD) is a digital circuit implementation platform that can be configured by the end user to implement a logic circuit of their choice. The two most common types of PLDs are field-programmable gate arrays (FPGAs) and complex programmable logic devices (CPLDs). Many PLD vendors provide computed-aided design tools to help their customers to implement logic designs in their PLDs. One type of PLD, the FPGA, is used as an example to illustrate the present invention. It should be noted that, in addition to PLDs, the present invention is applicable to other integrated circuit implementation technologies, for example, application specific integrated circuits (ASICs), mask-programmed gate arrays and standard cell devices.
In a typical architecture, an FPGA includes an array of configurable logic blocks (CLBs) surrounded by programmable input/output blocks (IOBs). The CLBs and IOBs are interconnected by a hierarchy of programmable routing resources, which are comprised of metal wire segments and programmable routing switches, also referred to as programmable interconnection points (PIPs). These CLBs, IOBs, and programmable routing resources are customized by loading a configuration bitstream into the FPGA. State-of-the art FPGAs contain tens of thousands of CLBs. For such devices, the task of establishing the required interconnections between the primitive cells inside a CLB and between the CLBs themselves becomes so onerous that it can only be accomplished with the assistance of computed-aided design tools. Accordingly, the manufacturers of FPGAs, including the assignee hereof, Xilinx, Inc., have developed place and route software tools which may be used by end customers to implement their respective designs in their FPGAs.
The time to execute conventional routing software (also called a router) can be very long, e.g., many hours. A typical design needs numerous iterations in testing and modification, and each iteration requires running the routing software. As a result, design cycles are affected by the execution time of the routing software. Consequently, there is a need to improve the execution time of routing software.